"""
栈Stack的实现主要有两类：
    用数组Array类实现
    用链表Linklist实现
    另外可以借助导入其他库来实现：
        collection -> deque
        queue -> LifoQueue
"""

"""
    用数组Array类型实现栈
"""
Stack_Array = []
# 用.append方法实现入栈
Stack_Array.append("a")
Stack_Array.append("b")
Stack_Array.append("c")
print("入栈后stack:")
print(*Stack_Array)
# 用.pop方法实现出栈
Stack_Array.pop()
Stack_Array.pop()
Stack_Array.pop()
print("出栈后stack:")
print(*Stack_Array)


"""
    用链表Linklist实现栈
"""
class Node:
    def __init__(self, value):
        """
            初始化为[ target_list | next ]
        """
        self.value = value
        self.next = None

class Stack:
    def __init__(self):
        self.head = Node("head")    # 初始化添加一个["head"|·]结点
        self.size = 0   # 只有头结点时栈长记0

    def __str__(self):
        """
            栈值Str化输出
            E.X.:Input:[ head | · ]->[ data1 | · ]->[ data2 | None ]
                 Output:"data1->data2"
        """
        cur = self.head.next
        out = ""    # 输出值在空栈时为空
        while cur:
            out += str(cur.value) + "->"
            cur = cur.next
        return out[:-2]  # 输出时去掉最后一个->

    def getSize(self)->int:
        """
            返回栈长
        """
        return self.size

    def isEmpty(self)->bool:
        """
            返回是否空栈的逻辑值
        """
        return self.size == 0

    # Get the top item of the stack
    def peek(self):
        """
            返回栈顶元素值
        """
        if self.isEmpty():
            return None  # 空栈时返回None
        return self.head.next.value

    def push(self, value):
        """
            压栈：将value添加在栈顶
        """
        node = Node(value)
        node.next = self.head.next  # 新节点指向原头结点的后继节点(原栈顶)
        self.head.next = node  # 头结点指向新节点
        self.size += 1  # 栈长+1

    def pop(self):
        """
            出栈：栈顶元素节点删除，返回栈顶元素value
        """
        if self.isEmpty():  # 栈空时抛出异常
            raise Exception("Popping from an empty stack")
        remove = self.head.next
        self.head.next = remove.next    # 头结点指向原栈顶元素的后继
        self.size -= 1
        return remove.value


"""
    课上测试
"""
stack = Stack()
# 压栈后输出当前栈
for i in range(1, 11):
    stack.push(i)
print(f"Stack: {stack}")
# 依次出栈，出栈时打印出栈元素
for temp in range(1, 6):
    top_value = stack.pop()
    print(f"Pop: {top_value}")
print(f"\nStack: {stack}")


"""
    其他的实现方法
"""
from collections import deque
Stack_collection = deque()

from queue import LifoQueue
stack_queue = LifoQueue(maxsize=3)

